package data_struct

import (
	"fmt"
)

//数据结构，图 的存储和遍历， 1，邻接矩阵
//图的概念：顶点，有向图（弧（弧头，弧尾），权值），无向图（边，权值）
/* 图示
        A
       / \
      B   D
     / \ / \
    C  F G-H
    \ /
     E
矩阵示例
  A B C D E F G H
A 0 1 0 1 0 0 0 0
B 1 0 1 0 0 1 0 0
C 0 1 0 0 1 0 0 0
D 1 0 0 0 0 0 1 1
E 0 0 1 0 0 1 0 0
F 0 1 0 0 1 0 0 0
G 0 0 0 1 0 0 0 1
H 0 0 0 1 0 0 1 0
*/
type MNode struct {
	Data      interface{} //顶点数据
	isVisited bool        //是否被访问过
}
type MMap struct {
	Capacity  int     //最多容纳的顶点个数
	nodeCount int     //已添加顶点数
	nodeArray []MNode //顶点数组
	matrix    []int   //邻接矩阵的数组
}

//初始化一个图
func MakeMap(size int) MMap {
	m := MMap{
		Capacity: size,
	}
	m.nodeArray = make([]MNode, size)
	m.matrix = make([]int, size*size)
	return m
}

//添加节点
func (t *MMap) AddNode(node MNode) bool {
	t.nodeArray[t.nodeCount].Data = node.Data
	t.nodeCount++
	return true
}

//重置节点状态为未访问
func (t *MMap) ResetNode() {
	for i := t.nodeCount - 1; i >= 0; i-- {
		t.nodeArray[i].isVisited = false
	}
}

//为有向图设置邻接矩阵
func (t *MMap) SetValutToMatrix2DirectedGraph(row int, col int, val int) bool {
	if row < 0 || row >= t.Capacity || col < 0 || col > t.Capacity {
		return false
	}
	t.matrix[row*t.Capacity+col] = val
	return true
}

//为无向图设置邻接矩阵. （双向，对角线对称）
func (t *MMap) SetValutToMatrix2UnDirectedGraph(row int, col int, val int) bool {
	if row < 0 || row >= t.Capacity || col < 0 || col > t.Capacity {
		return false
	}
	t.matrix[row*t.Capacity+col] = val
	t.matrix[col*t.Capacity+row] = val
	return true
}

//从邻接矩阵中取值
func (t *MMap) getMatrixValue(row int, col int) int {
	return t.matrix[row*t.Capacity+col]
}

//深度优先访问。给一个节点，向一个方向一直向下遍历，直到没有下一个点，或形成回环。再向另一个方向继续
// ABCEFDGH
func (t *MMap) DepthTraverse(nodeIndex int) {
	node := &(t.nodeArray[nodeIndex])
	node.isVisited = true

	fmt.Print(node.Data)
	for i := 0; i < t.Capacity; i++ {
		if t.getMatrixValue(i, nodeIndex) != 0 { //表示该点和当前点相连，则访问
			if t.nodeArray[i].isVisited { //已访问过的不再访问，避免回环
				continue
			}
			t.DepthTraverse(i)
		}
	}
}

// 带返回值 的
func (t *MMap) DepthTraverse2(nodeIndex int) (r []interface{}) {
	node := &(t.nodeArray[nodeIndex])
	node.isVisited = true

	r = append(r, node.Data)
	for i := 0; i < t.Capacity; i++ {
		if t.getMatrixValue(i, nodeIndex) != 0 { //表示该点和当前点相连，则访问
			if t.nodeArray[i].isVisited { //已访问过的不再访问，避免回环
				continue
			}
			nvs := t.DepthTraverse2(i)
			for _, v := range nvs {
				r = append(r, v)
			}
		}
	}
	return
}

//广度优先： 向每一个方向访问一次。 再次访问得到的节点的下一层
func (t *MMap) BreadthTraverse(nodeIndex int) {
	node := &(t.nodeArray[nodeIndex])
	node.isVisited = true
	fmt.Print(node.Data)
	// 辅助函数.
	var breadthHelp func(prev []int)
	breadthHelp = func(prev []int) {
		var currIndexs = []int{}
		for i := 0; i < len(prev); i++ {
			for j := 0; j < t.Capacity; j++ {
				if t.getMatrixValue(j, prev[i]) != 0 {
					//找到与给定的点相边的顶点，打印，放入数组，准备下次使用
					node1 := &(t.nodeArray[j])
					if node1.isVisited {
						continue
					}
					node1.isVisited = true
					fmt.Print(node1.Data)
					currIndexs = append(currIndexs, j)
				}
			}
		}
		if len(currIndexs) > 0 {
			breadthHelp(currIndexs)
		}
	}
	breadthHelp([]int{nodeIndex})
}

//打印邻接矩阵
func (t *MMap) PrintMatrix(helper bool) {
	if helper {
		fmt.Print("  ")
		for i := 0; i < t.Capacity; i++ {
			fmt.Print(t.nodeArray[i].Data)
			if i < t.Capacity-2 {
				//fmt.Println(" ")
			}
		}
		fmt.Println()
	}
	for i := 0; i < t.Capacity; i++ {
		if helper {
			fmt.Print(t.nodeArray[i].Data, " ")
		}
		for j := 0; j < t.Capacity; j++ {
			fmt.Print(t.matrix[i*t.Capacity+j])
			if j != t.Capacity-1 {
				fmt.Print(" ")
			}
		}
		fmt.Println()
	}
}